package backtracking;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @description: <a href="https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj">17. 电话号码的字母组合</a>
 * @author: zhaoyinglin
 * @date: 2024/3/5
 */
public class LetterCombinations {

    public static void main(String[] args) {
        LetterCombinations.Solution solution = new Solution();

        System.out.println(solution.letterCombinations("23"));
    }

    static class Solution {

        public List<String> letterCombinations(String digits) {

            List<String> result = new ArrayList<>();

            if (digits == null || digits.isEmpty()) {
                return result;
            }

            Map<String, String> charsMap = new HashMap<>();

            charsMap.put("2", "abc");
            charsMap.put("3", "def");
            charsMap.put("4", "ghi");
            charsMap.put("5", "jkl");
            charsMap.put("6", "mno");
            charsMap.put("7", "pqrs");
            charsMap.put("8", "tuv");
            charsMap.put("9", "wxyz");

            backTracking(charsMap, 0, digits, new StringBuilder(), result);

            return result;
        }

        private void backTracking(Map<String, String> charsMap, int index, String digits, StringBuilder joinString, List<String> result) {

            if (index == digits.length()) {
                result.add(joinString.toString());
                return;
            }

            String num = String.valueOf(digits.charAt(index));

            String chars = charsMap.get(num);

            for (int i = 0; i < chars.length(); i++) {

                joinString.append(chars.charAt(i));

                backTracking(charsMap, index + 1, digits, joinString, result);

                joinString.deleteCharAt(index);

            }
        }
    }

}
